class Solution {
public:
    int numIslands(vector<vector<char>>& grid)
    {
        int ret = 0;
        int m = grid.size(), n = grid[0].size();

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1')
                {
                    ret++;
                    help(grid, i, j);
                }
            }
        }

        return ret;
    }
    void help(vector<vector<char>>& grid, int m, int n)
    {
        if (m >= grid.size() || n >= grid[0].size() || m < 0 || n < 0 || grid[m][n] != '1') return;

        grid[m][n] = '2';
        help(grid, m + 1, n);
        help(grid, m, n + 1);
        help(grid, m - 1, n);
        help(grid, m, n - 1);
    }
};